package algorithm7.leetcode.队栈;

import java.util.Stack;

public class LC32 {

/*
https://leetcode.cn/problems/longest-valid-parentheses/description/

32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0
 */

    class Solution {

        public int longestValidParentheses(String s) {
            char[] charArray = s.toCharArray();
            int maxLen = 0;
            // 下标
            Stack<Integer> stack = new Stack<>();
            // 先放一个占位，如果右括号比左括号多，-1将出栈，此时栈为空，代表有效括号被右括号分隔，需要从当前位置重新计算长度(curLen=0)
            stack.push(-1);
            for (int i = 0; i < charArray.length; i++) {
                if (charArray[i] == '(') {
                    stack.push(i);
                }
                if (charArray[i] == ')') {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        maxLen = Math.max(maxLen, i - stack.peek());
                    }
                }
            }
            return maxLen;
        }

    }

}
